public class code02 {
//    力扣 150 二叉树展开为链表
public void flatten(TreeNode root) {
    // 解法一：通过移动的方式，在树原有的基础上进行移动

    // 1. 从第二层开始，将左子树插入到右子树的位置上
    // 2. 将原先的右子树接到新插入的右子树的后面
    // 3. 考虑新的右子树的节点，将上面的步骤进行重复

    while(root != null) {

        // 第一步，判断左子树的情况
        if(root.left == null) {
            root = root.right;
        } else {
            // 当这个左子树存在时，此时就需要找到该左子树的右边最后的一个节点
            TreeNode p = root.left;
            while(p.right != null) {
                // 不断的寻找最右侧的最后一个节点
                p = p.right;
            }

            // 找到左子树的最后最右侧的节点后，将 root 上的右子树拼接到当前找到的节点处
            p.right = root.right;

            // 此时将 root 的左侧节点接到右侧来
            root.right = root.left;
            root.left = null;

            // 再来考虑下一个节点
            root = root.right;
        }
    }
}
}
